package Demo2_2;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User：Lenovo
 * Date:2025-02-02
 * Time:19:35
 */
// 定义二叉树节点类
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public class InvertBinaryTree {
    // 翻转二叉树的方法
    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        // 交换当前节点的左右子树
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;

        // 递归翻转左子树
        invertTree(root.left);
        // 递归翻转右子树
        invertTree(root.right);

        return root;
    }

    // 辅助方法：用于打印二叉树（前序遍历）
    public void preOrderTraversal(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print(root.val + " ");
        preOrderTraversal(root.left);
        preOrderTraversal(root.right);
    }

    public static void main(String[] args) {
        // 构建一个简单的二叉树
        TreeNode root = new TreeNode(4);
        root.left = new TreeNode(2);
        root.right = new TreeNode(7);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(3);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(9);

        InvertBinaryTree solution = new InvertBinaryTree();

        // 打印原始二叉树
        System.out.print("Original tree (pre-order traversal): ");
        solution.preOrderTraversal(root);
        System.out.println();

        // 翻转二叉树
        TreeNode invertedRoot = solution.invertTree(root);

        // 打印翻转后的二叉树
        System.out.print("Inverted tree (pre-order traversal): ");
        solution.preOrderTraversal(invertedRoot);
        System.out.println();
    }
}
